import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Solve {
    // 输出二叉树的右视图
    // https://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0?tpId=295&tqId=1073834&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    private int index;
    public int[] solve (int[] preOrder, int[] inOrder) {
        // write code here
        index = 0;
        TreeNode root = buildTreeNode(preOrder, inOrder, 0, preOrder.length-1);
        if (root == null) {
            return new int[]{};
        }
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        List<Integer> ret = new ArrayList<>();
        while (!deque.isEmpty()) {
            int result = 0;
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.poll();
                result = node.val;
                if (node.left != null) {
                    deque.offer(node.left);
                }
                if (node.right != null) {
                    deque.offer(node.right);
                }
            }
            ret.add(result);
        }
        return ret.stream().mapToInt(Integer::intValue).toArray();
    }

    private TreeNode buildTreeNode(int[] preOrder, int[] inOrder, int left, int right) {
        if (left > right) {
            return null;
        }
        TreeNode node = new TreeNode(preOrder[index]);
        int pivot = findIndex(inOrder, left, right, preOrder[index++]);
        node.left = buildTreeNode(preOrder, inOrder, left, pivot-1);
        node.right = buildTreeNode(preOrder, inOrder, pivot+1, right);
        return node;
    }

    private int findIndex(int[] inOrder, int left, int right, int target) {
        for (int i = left; i <= right; i++) {
            if (inOrder[i] == target) {
                return i;
            }
        }
        return -1;
    }
}
